function MapNode(m,x,y){ // A node for the Map class
	this.map = m;
	this.x = x||0;
	this.y = y||0;
	this.contents = [];
}
MapNode.prototype.type   = 0;
MapNode.prototype.f      = 0;
MapNode.prototype.g      = 0;
MapNode.prototype.h      = 0;
MapNode.prototype.closed = false;
MapNode.prototype.visited= false;
MapNode.prototype.parent = null;
MapNode.prototype.insert = function(o){ // insert a sprite into the map node
	if (o===null || o in this.contents)
		return;
	this.contents.push(o);
}
MapNode.prototype.remove = function(o){ // remove a sprite from the map node
	var i = this.contents.indexOf(o);
	if (i > -1)
		this.contents.splice(i,1);
}
MapNode.prototype.isWall = function(){
	return this.map.types[this.type].speed <= 0; // anything below 0 is available as a path
}
function Map(w,h,b){ // map for collision detection and quick path finding
    this.list = [];
    this.map = {};
	this.reset(w,h,b);
	this.distance  = Map.distance2d;
	this.heuristic = Map.Manhattan;
	this.collision = Map.radialCollision;
	this.types = {
		"NONE" : { "value": 0,	"speed":1},
		"WALL" : { "value": 1,	"speed":0}
	}
}
Map.nodeSort = function(a,b){ // used to sort the stack for the path detection
	var f = b.f-a.f;
	return !f?Math.random()*2-1:f; // random makes sure the path isn't too predictable
}
Map.distance2d = function(a,b){ // distance between two sprites
    if (!a || !b){
        return 0;
    }
	return (Math.sqrt(Math.pow(a.x-b.x,2)+Math.pow(a.y-b.y,2)));
}
Map.radialCollision = function (a,b){ // checks if items a and b collide based on radius
    if (!a || !b)
		return false;
	return (Math.abs(a.y-b.y)-a.r-b.r<=0 && Math.abs(a.x-b.x)-a.r-b.r<=0);
}
Map.Manhattan = {
	heuristic : function(a,b){ // manhattan heuristic for path finding (2d 4-way movements)
		return (Math.abs(b.x-a.x)+Math.abs(b.y-a.y));
	},
	adjacent  : function (n){
		var aj=[],
			m = this.map,
			x = n.x,
			y = n.y,
			a = m[(x+1)+":"+y];
		if (a) aj.push(a);
		if (a = m[(x-1)+":"+y]) aj.push(a);
		if (a = m[x+":"+(y-1)]) aj.push(a);
		if (a = m[x+":"+(y+1)]) aj.push(a);
		return aj;
	}
}
Map.prototype.blockSize = 10;
Map.prototype.getNode = function (x,y){
	return this.map[x+":"+y];
}
Map.prototype.getNodeAt = function (x,y){
	return this.map[Math.floor(x/this.blockSize)+":"+Math.floor(y/this.blockSize)];
}
Map.prototype.reset=function(w,h,b){ // creates a completely clean map
	w = w || this.w || 300;
	this.w = w;
	h = h || this.h || 300;
	this.h = h;
	b = b || this.blockSize|| 20;
	this.blockSize = b;
	m = this.map = [];
	for (var i=Math.ceil(w/b);i--;){
		for (var j=Math.ceil(h/b);j--;){
			m[i+":"+j] = new MapNode(this,i,j);
		}
	}
	this.list = [];
}
Map.prototype.clear = function(){ // clears the sprites from the map
    for (var l = this.list, i=l.length; i--;){
		var li = l[i];
		li.contents = [];
		delete li;
    }
    this.list = [];
}
Map.prototype.insert = function(o){ // insert a sprite into the map (object must contain x and y coordinates (returns the node that contains the item)
    var mx = Math.floor(o.x/this.blockSize), my = Math.floor(o.y/this.blockSize), node = this.map[mx+":"+my], l = this.list, i=l.length;
	if (!node)
		return null;
    for (;i--;){ // check if it's in the list
        var item = l[i];
        if (item.o == o){
            var index = item.n.indexOf(o);
            if (item.n === node){ // already in the right place
                return node;
            }
			item.n.remove(o); // move to new node
			item.n = node;
            node.insert(o);
            return node;
        }
    }
    l.push({"o":o,"n":node});
    node.push(o);
	return node;
};
Map.prototype.remove = function(o){ // remove an object from the map
    if (!o) return;
    var mx = Math.floor(o.x/this.blockSize), my = Math.floor(o.y/this.blockSize), node, l = this.list, i=l.length;
    for (;i--;){
        if (l[i].o == o){
            var item = l.splice(i,1)[0];
			item.n.remove(o);
            return;
        }
    }
};
Map.prototype.checkCollisions = function(o){ // checks objects that collide with the requested object (o does not have to be from the map)
    if (!o){
        return [];
    }
    var parts = this.checkNearby(o,1), collisions = [];
    for (var i=parts.length; i--;){
        var p = parts[i];
        if (p != o && this.collision(o,p)){
            collisions.push(p);
        }
    }
    return collisions;
};
Map.prototype.checkNearby = function(o,r){ // gets all the items within a specific map area (square not circular)
    if (this.list.length < 1 || !o){
        return [];
    }
    var mx = Math.floor(o.x/this.blockSize), my = Math.floor(o.y/this.blockSize), parts = [], l = this.list;
    for (var i=r+1;i-->-r;){
        for (var j=r+1;j-->-r;){
            var mp = this.map[(mx+i)+":"+(my+j)];
            if (mp){
                parts = parts.concat(mp.contents);
            }
        }
    }
    return parts;
};
Map.prototype.getBorder = function(mx,my,r){ // gets the blocks that are r blocks away from the center
    var parts = [], abs = Math.abs, x=0;
    for (var i=r+1;i-->-r;){
        var air = abs(i)==r;
        for (var j=r+1;j-->-r;){
            if (air || abs(j)==r){
                x++;
                var mp = this.map[(mx+i)+":"+(my+j)];
                if (mp){
                    parts = parts.concat(mp.contents);
                }
            }
        }
    }
    return parts;
}
Map.prototype.getNearest = function (o, m){ //gets the nearest sprite, not exact, but not bad for the purpose
    var l = this.list;
    if (l.length < 1){
        return null;
    }
    if (l.length == 1){
        return l[0].o;
    }
    var self = this, mx = Math.floor(o.x/this.blockSize), my = Math.floor(o.y/this.blockSize), collisions = [], dist = 1000, nearest = null, r=0, mr = Math.ceil((m||200)/this.blockSize), parts=[];
    while (r++<mr && parts.length == 0){
        parts = this.getBorder(mx,my,r);
    }
    for (var i=parts.length; i--;){
        var p = parts[i],d;
        if (p === o)
            continue;//ignore self
        d=this.distance(o,p);
        if (d < dist){
            nearest = p;
            dist = d;
        }
    }
    return nearest;
};
Map.prototype.clearPath=function(){ // removes all previous path data
	var m = this.map;
	for (var i in m){
		var n = m[i];
		n.parent = null;
		n.visited = false;
		n.closed = false;
		n.h = null;
		n.f = null;
		n.g = null;
	}
	this.list = [];
}
Map.prototype.bestMove = function (start,end,h){
	var path = this.makePath(start,end,h);
	return path?path[0]:false;
}
Map.prototype.makePath = function (start,end){ // creates a path the the end
	if (!start || !end)
		return [];
	if (start == end){
		return [];
	}
	this.clearPath();
	var heap = [],
		h    = this.heuristic,
		hsort= Map.nodeSort,
		hu   = h.heuristic,
		ad   = h.adjacent,
		di   = this.distance,
		i;
	heap.push(start);
	start.g = 0;
	for(;heap.length;){
		var c = heap.pop();
		if (c == end){
			var r = [];
			while(c.parent) {
				r.push(c);
				c = c.parent;
			}
			return r.reverse();
		}
		c.closed = true
		var adj=ad.apply(this,[c]),
			//spd = , // allowing for varying speeds
			g = c.g;
		for (i = adj.length; i--;){
			var a = adj[i];
			if (a.closed || a.isWall()) continue;
			if (!a.visited || g < a.g){
				var spd = this.types[a.type].speed;
				a.g = g+1/(spd>0?spd:1);
				a.h = a.h || hu.apply(this,[a,end]);
				a.f = a.g + a.h;
				a.parent = c;
				if (!a.visited)
					heap.push(a);
				a.visited = true;
			}
		}
		heap.sort(Map.nodeSort);
	}
	return [];
}